//
// Created by apple on 2021/5/25.
//

#include <iostream>
#include "vector"

using namespace std;

void QuickSort(vector<int> &array, int low, int high) {
    if (low >= high)
        return;
    int i = low, j = high, index = array[i];
    while (i < j) {
        while (i < j && array[j] >= index)  // 在i和j不重叠的情况下, 通过滑动j查找小于index的目标
            j--;
        if (i < j)
            array[i++] = array[j];  // 通过滑动j查找到小于index的数后，将其填入到array[i]的坑位，并且让i向右边移动一位
        while (i < j && array[i] < index)   // 通过滑动i查找大于index的目标
            i++;
        if (i < j)
            array[j--] = array[i];  // 把滑动i找到的大于index的目标填入array[j]的坑位中， 并让j向左边移动一位
    }
    array[i] = index;   // 将基准数填入最后一个坑位
    QuickSort(array, low, i - 1);       // 左边分治
    QuickSort(array, i+1, high);        // 右边分治
}

void QuickSort(vector<int> &array) {
    if (array.size() == 0)
        return;
    QuickSort(array, 0, array.size() - 1);
}

int main() {
    std::cout << "Quick Sort" << std::endl;
    vector<int> s = {23, 34, 9,23, 234, 1, 312, 3, 6};
    QuickSort(s);
    for (int i = 0; i < s.size(); ++i) {
        cout << s[i] << " ";
    }
    return 0;
}